package algorithm.leetcode.medium;

/*
 运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制 。
 */

import java.util.HashMap;
import java.util.Map;

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/12/4
 */
public class Question146 {

    public static void main(String[] args) {

    }


    private class LRUCache {
        private Map<Integer, LinkedNode> cache;
        private int size;
        private int capacity;
        private LinkedNode head;
        private LinkedNode tail;

        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.size = 0;
            this.cache = new HashMap<>(10);
            head = new LinkedNode();
            tail = new LinkedNode();
            head.next = tail;
            tail.pre = head;
        }

        public int get(int key) {
            LinkedNode node = cache.get(key);
            if (node == null) {
                return -1;
            }
            // 将这个节点移动到头部
            moveToHead(node);
            return node.value;
        }

        public void put(int key, int value) {
            LinkedNode node = cache.get(key);
            if (node == null) {
                // 如果key不存在，创建一个节点
                LinkedNode newNode = new LinkedNode(key, value);
                // 添加哈希表
                cache.put(key, newNode);
                // 添加至头部
                addToHead(newNode);
                size++;
                if (size > capacity) {
                    // 如果当前容量大于了所定义的容量则删除最尾部（最近未被使用）
                    LinkedNode tail = removeTail();
                    // 同时在哈希表中移除
                    cache.remove(tail.key);
                    size--;
                }
            } else {
                // 说明key存在，修改value并移动至头部
                node.value = value;
                moveToHead(node);
            }
        }

        private void moveToHead(LinkedNode node) {
            removeNode(node);
            addToHead(node);
        }

        private void removeNode(LinkedNode node) {
            node.next.pre = node.pre;
            node.pre.next = node.next;
        }

        /**
         * 移除最后一个节点并返回
         */
        private LinkedNode removeTail() {
            LinkedNode node = tail.pre;
            removeNode(node);
            return node;
        }

        /**
         * 将该节点添加至头部
         */
        private void addToHead(LinkedNode newNode) {
            newNode.pre = head;
            newNode.next = head.next;
            head.next.pre = newNode;
            head.next = newNode;
        }


    }

    /**
     * 头部是最近被使用的
     * 尾部是最近未使用的
     */
    private class LinkedNode {
        int key;
        int value;
        LinkedNode pre;
        LinkedNode next;

        public LinkedNode() {
        }

        public LinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
}
